package com.li.sort.arithmetic;

import java.util.Random;

public class MinHeap {
	public static final int SIZE = 100000000;
	public static void main(String []args){
		int[] a = new int[SIZE];
		Random random = new Random();
		for(int i = 0;i < SIZE ;i++){
			a[i] = random.nextInt(100);
		}
		a[10000]= 100;
		a[646464] = 100;
		long startTime = System.currentTimeMillis();
		int result[] = getTopKByHeap(a, 3);
		for (int temp : result) {
			System.out.print(temp+" ");
		}
		System.out.println("用时"+(System.currentTimeMillis()-startTime));
	}
	/**
	 * 创建k个节点的小根堆
	 * @param a
	 * @param k
	 * @return
	 */
	public static int[] createHeap(int a[], int k) {
		int[] result = new int[k];
		for (int i = 0; i < k; i++) {
			result[i] = a[i];
		}
		for (int i = 1; i < k; i++) {
			int child = i;
			int parent = (i - 1) / 2;
			int temp = a[i];
			while (parent >= 0 &&child!=0&& result[parent]>temp) {
				result[child] = result[parent];
				child = parent;
				parent = (parent - 1) / 2;
			}
			result[child] = temp;
		}
		return result;
	}

	public static void insert(int a[], int value) {
		a[0]=value;
		int parent=0;

		while(parent<a.length){
			int lchild=2*parent+1;
			int rchild=2*parent+2;
			int minIndex=parent;
			if(lchild<a.length&&a[parent]>a[lchild]){
				minIndex=lchild;
			}
			if(rchild<a.length&&a[minIndex]>a[rchild]){
				minIndex=rchild;
			}
			if(minIndex==parent){
				break;
			}else{
				int temp=a[parent];
				a[parent]=a[minIndex];
				a[minIndex]=temp;
				parent=minIndex;
			}
		}

	}

	public static int[] getTopKByHeap(int input[], int k) {
		int heap[] = createHeap(input, k);
		for(int i=k;i<input.length;i++){
			if(input[i]>heap[0]){
				insert(heap, input[i]);
			}
		}
		return heap;

	}


}
